内田 1章集合と写像

SS1. 集合とは

集合

元の集まり

集合$ Aみたいな書き方をする

厳密で主流な定義は、ZFC公理系をすべて満たす項のこと

集合の表現

外延的定義

書き並べる

$ \{1, 2, 3\}

内包的定義

ある条件を満たす元の集合

$ \{x | xは条件$ Pを満たす$ \}

集合の種類

空集合

Texだと、$ \phi, \emptyset, \varnothingなどで表す

$ \phiは紛らわしいのでやめたほうがいいtakker.icon

穴の半径wogikaze.icon

薄汚いオルフェノクtakker.icon

有限集合

元の個数が0個以上の集合

個数の厳密な定義は2章を参照takker.icon

無限集合

有限集合以外の集合

集合の関係

部分集合

$ A \subset Bor $ A\subseteq B

AはBの部分集合

AとBが同じ集合の時も成り立つ

真部分集合

$ A \subset Bかつ$ A \not = B

$ A\subsetneq Bとも書く

演習

問1.1

教科書に回答あり

biwa.icon

成立する: 1, 2, 3, 7, 8

問1.2

教科書に回答あり

biwa.icon

C, E, F

B, D

問1.3

教科書に回答あり

biwa.icon

成立する: 2, 3, 4, 6

これここでの解答の書き方迷うなbiwa.icon

隠すべきか

人ごとに分けるべきか

3人以上になったら分ければいいと思うtakker.icon

2人程度なら隠すまでもない

すぐ答えを出せなくて、自力で解きたい問題があれば、自分のprojectで解けばいい

確かに、それで行きますbiwa.icon

SS2. 集合の演算

問2.1

教科書回答なし

問2.2

問2.3

教科書回答なし

回答biwa.icon

$ A_1 \subset Aと仮定する(1)

$ x \in A_1 - Bと仮定する(2)

仮定(2)より、$ x \in A_1かつ$ x \not \in B_1.

仮定(1)と$ x \in A_1より、$ x \in A

よって、$ x \in A かつ $ x \not \in Bより、$ x \in A - B.

$ A_1 - B\subset A - B.

$ B_1 \subset Bと仮定する(1)

$ x \in A - Bと仮定する(2)

仮定(2)より、$ x \in Aかつ$ x \not \in B.

仮定(1)は変形すると、$ x \not \in Bならば、$ x \not \in B_1.

$ x \not \in Bなので、$ x \not \in B_1.

$ x \in Aかつ$ x \not \in B_1より、$ x \in A - B_1.

$ A - B \subset A - B_1.

takker.icon

$ \forall A,B\forall A_1\subseteq A;A_1\setminus B\subseteq A\setminus Bを示す

$ A_1\subseteq A

$ \iff\forall x;(x\in A_1\implies x\in A)

$ \implies\forall x;(x\in A_1\land x\notin B\implies x\in A\land x\notin B)

$ \iff\forall x;(x\in A_1\setminus B\implies x\in A\setminus B

$ \underline{\iff A_1\setminus B\subseteq x\in A\setminus B\quad}_\blacksquare

$ \forall A,B\forall B_1\subseteq B; A\setminus B\subseteq A\setminus B_1を示す

$ B_1\subseteq B

$ \iff\forall x;(x\in B_1\implies x\in B)

$ \iff\forall x;(x\notin B\implies x\notin B_1)

$ \implies\forall x;(x\in A\land x\notin B\implies x\in A\land x\notin B_1)

$ \iff\forall x;(x\in A\setminus B\implies x\in A\setminus B_1

$ \underline{\iff A\setminus B\subseteq x\in A\setminus B_1\quad}_\blacksquare

問2.4

教科書回答あり

biwa.icon

まず、$ A - B = A \Rightarrow Aと$ Bが交わらないことを示す

$ A - B = Aと仮定する

すなわち、$ x \in A \land x \not \in B \Leftrightarrow x \in A .

この時、$ A \cap B = \{x | x \in A \land x \in B\}.

$ = \{x | x \in A \land x \not \in B \land x \in B\}.

$ = \phi

$ x \not \in Bと$ x \in Bを同時に満たす$ xは存在しないので

$ A - B = A \Rightarrow A \cap B = \phiであると示せた

ここもっとスマートにいけそうbiwa.icon

次に逆を示す

$ A \cap B = \phiと仮定する。

$ A = (A - B) \cup (A \cap B) = (A - B) \cup \phi = A -B.

takker.icon

$ \forall A,B;A\setminus B=A\iff A\cap B=\varnothingを示す

$ \forall A,Bにて

$ A\setminus B=A\iff \forall x;(x\in A\land x\notin B\iff x\in A)

$ \iff \forall x;(x\in A\implies x\in A\land x\notin B)

$ \because x\in A\land x\notin B\implies x\in Aは常に成り立つ

$ \iff \forall x;(x\in A\implies x\notin B)

$ \iff \forall x;(x\notin A\lor x\notin B)

$ \iff \forall x;\lnot(x\in A\land x\in B)

$ \iff \lnot\exists x;x\in A\cap B

$ \iff A\cap B=\varnothing

$ \underline{\therefore\forall A,B;A\setminus B=A\iff A\cap B=\varnothing\quad}_\blacksquare

集合演算だけで示せたらもっとスマート

問2.5

問2.6

SS3. ド・モルガンの法則

SS4. 直積集合

SS5 写像

問5.1

定理5.2

Schröder–Bernsteinの定理で必要になりそうなものを証明しておくtakker.icon

$ f:A\to Bとする

(7)

$ f[A_1]\setminus f[A_2]

$ = \{b\in B|\exist a\in A\cap A_1.b=f(a)\}\setminus\{b\in B|\exist a\in A\cap A_2.b=f(a)\}

$ = \{b\in B|\exist a\in A\cap A_1.b=f(a)\land\lnot\exist a\in A\cap A_2.b=f(a)\}

$ = \{b\in B|\exist a\in A\cap A_1.b=f(a)\land\forall a\in A\cap A_2.b\neq f(a)\}

$ \subseteq\{b\in B|\exist a\in A\cap A_1.b=f(a)\land(a\in A\cap A_2\implies b\neq f(a))\}

$ =\{b\in B|\exist a\in A\cap A_1.(b=f(a)\land a\notin A\cap A_2)\lor f(a)=b\neq f(a)\}

$ =\{b\in B|\exist a\in A\cap A_1.b=f(a)\land a\notin A\cap A_2\}

$ =\{b\in B|\exist a\in A\cap(A_1\setminus A_2).b=f(a)\}

$ \underline{=f[A_1\setminus A_2]\quad}_\blacksquare

問5.2

このあたりエグいので解いておきたいtakker.icon

わかる。えぐいよねbiwa.icon

頑張って途中まで解いたら数学の先生に聞こうと思ってるbiwa.icon

解答が書いてあれば、数学の先生に合ってるか聞きます。

いや、単に定義通り展開するだけだから、たいしたことないかtakker.icon

$ x\in \left(\bigcup_{\lambda\in\Lambda}A_\lambda\right)\cap B

$ \iff (\exists\lambda\in\Lambda; x\in A_\lambda)\land x\in B

$ \iff \exists\lambda\in\Lambda;(x\in A_\lambda\land x\in B)

ここの展開は別途証明したほうがよさそう

$ \iff \exists\lambda\in\Lambda;(x\in A_\lambda\cap B)

$ \iff x\in\bigcup_{\lambda\in\Lambda}A_\lambda\cap B

$ \therefore \forall A,B,\Lambda;\left(\bigcup_{\lambda\in\Lambda}A_\lambda\right)\cap B=\bigcup_{\lambda\in\Lambda}A_\lambda\cap B

大したことなかった

自分のScrapbox覗いたら、全く同じように解いてたbiwa.icon

問5.3

$ (\bigcup_{\lambda \in \Lambda} A_\lambda)^c = \bigcap_{\lambda \in \Lambda}(A_\lambda^c) を示す。

$ x \in (\bigcup_{\lambda \in \Lambda} A_\lambda)^c,

$ \Leftrightarrow x \in X - \bigcup_{\lambda \in \Lambda} A_\lambda,

$ \Leftrightarrow x \in Xかつ$ x \not \in \bigcup_{\lambda \in \Lambda} A_\lambda,

$ \Leftrightarrow x \in Xかつ$ \lnot (\exist \lambda \in \Lambda. x \in A_\lambda),

$ \Leftrightarrow x \in Xかつ$ \forall \lambda \in \Lambda.　x \not \in A_\lambda,

$ \Leftrightarrow \forall \lambda \in \Lambda. x \in X - A_\lambda,

$ \Leftrightarrow x \in \bigcap_{\lambda \in \Lambda}(A_\lambda^c).

え、これで大丈夫？前提条件を一切使わなかったので、どっかで間違ってそうbiwa.icon

なにか前提条件あったっけ？takker.icon

$ (A_\lambda|\lambda\in\Lambda)が$ Xの部分集合系biwa.icon

不要。Xは任意の集合で成立するtakker.icon

なるほどbiwa.icon

$ (\bigcap_{\lambda \in \Lambda}A_\lambda)^c = \bigcup(A_\lambda^c)を示す.

$ x \in (\bigcap_{\lambda \in \Lambda}A_\lambda)^c,

$ \iff x \in X - \bigcap_{\lambda \in \Lambda}{A_\lambda},

$ \iff x \in X \land \lnot (x \in \bigcap_{\lambda \in \Lambda}{A_\lambda}),

$ \iff x \in X \land \lnot(\forall \lambda. x \in A_\lambda),

$ \iff x \in X \land \exist \lambda.x \not \in A_\lambda,

$ \iff \exist \lambda.x \in X \land x \not \in A_\lambda,

$ \iff \bigcup_{\lambda \in \Lambda}(A_\lambda^c).

問5.4

(1) $ f(\bigcup_{\lambda \in \Lambda}A_\lambda) = \bigcup_{\lambda\in\Lambda }f(A_\lambda)を示す

$ f(\bigcup_{\lambda \in \Lambda}A_\lambda) = \{y \in Y | \exist x. x \in \bigcup_{\lambda \in \Lambda}A_\lambda \land y = f(x)\},

$ = \{y\in Y|\exist x \in X. \exist \lambda \in \Lambda. x \in A_\lambda \land y = f(x)\},

$ = \{u \in Y|\exist\lambda\in\Lambda.\exist x \in X. y = f(x)\},

$ = \bigcup_{\lambda\in\Lambda }f(A_\lambda).

こんな感じでいいのかな？biwa.icon

常に論証が不安

もっとパターンみたいなの覚えなきゃなんだろうな

イメージや解釈を作ってみるといいかもtakker.icon

問5.5

これは面倒くさいだけtakker.icon

誰かやって

やるか〜biwa.icon

問5.6

エグいのはこっちからでしたtakker.icon

無限が絡んでくるからやばい

「無限が絡んでくる」の怖いcFQ2f7LRuLYP.icon

因縁をつけるの絡む

と思ったけど、$ \forall,\exists使えば大したことないかも

$ \forallでも無限扱うの面倒くさくなかったっけ？biwa.icon

ちゃんと問題文読んで頑張ってみます

無限の論理命題を扱うのが面倒くさいみたいな話だった気がしてきた。

そしてこれは無限の論理命題を扱うような話ではない(そらそう)

上極限集合の定義

$ \limsup_{n\to\infty} E_n=\bigcap_{k\in\N}\bigcup_{k\le n}E_n

わーおtakker.icon

問題解くのは単に機械的に式展開するだけなのでいい。それよりこいつの解釈が大変そう

解釈に関する問い

なぜ$ \supなのか.

$ \sup Aで$ Aの上限を表す

どの特徴を「上極限」と呼んでいるのか

具体的にどんな集合が上極限集合になるのか

これに属する元の性質はこう

$ x\in \limsup_{n\to\infty} E_n\iff \forall k\in\N;x\in \bigcup_{k\le n}E_n \iff\forall k\in\N\exists n\ge k;x\in E_n

なるほどε-δ論法か。完全に理解した(大嘘)

上極限集合わからないbiwa.icon

これの嬉しさが、一体どういう特徴があるんだ。

なんでこんな定義してんの？

普通に本だけじゃわからないので、動画見ます

https://youtu.be/ioKPIMyFB1o

わかりやすかったのでおすすめです。

上極限集合は無限個$ E_nに属す元全体の集合である

ここの意味が取れなかったけれど、意味がわかった

$ x \in \limsup_{n\to\infin} E_nの時、$ x \in Aとなるような集合$ Aを$ E_nから無限に持って来れるんだな

内田 1章集合と写像#646ac4011280f00000fc47d5の$ \exists n\ge k;x\in E_nに相当する部分ですねtakker.icon

どんな$ kでも$ E_nが存在することが保証されていr

無限に持って来られればいいので、連続的に持っている必要はない

$ nが奇数の時だけ含む元とか、$ nが素数の時だけ含む元も、上極限集合に含まれる

↑の論理式で示すと、$ nが奇数の時だけ含む元なら$ kより大きい奇数で添字付けられた$ E_n(例えば$ E_{2k+1})を採用すればいいtakker.icon

具体例を出していこう

$ E_n = \{\{0\}, \{0, 1\}, \{0, 1, 2\}, \dots, \{0, 1, 2, \dots, n\}\}.

$ \forall s \in N. s \in \limsup_{n \to \infin} E_n.

$ E_n = \{\{0\}, \{1\}, \dots \{n\}\}.

$ \varnothing = \limsup_{n \to \infin}E_n.

$ E_n = \begin{cases} \{0\}&(nが素数)\\ \{n\} &\text{else} \end{cases}

$ 0 \in \limsup_{n \to \infin}{E_n}.

いいぞtakker.icon

下極限集合

$ \liminf_{n\to\infin}E_n = \bigcup^\infin_{k=1}\bigcap^\infin_{n=k}E_n.

$ x \in \bigcup^\infin_{k=1}\bigcap^\infin_{n=k}E_n \iff \exist k \geq 1. \forall n \geq k. x \in E_n.

ある地点$ kから先の全ての集合に属している

こっちは上極限集合と違って、連続的に持っている必要がある

下極限集合に属すには、$ A_kに属していたならば、$ A_{k+1}, $ A_{k+2}, $ A_{k+...}とずっと持っている必要がある

上極限集合と下極限集合の嬉しさは一体何biwa.icon

問5.6

(1)$ \liminf_{n\to\infty}E_n\subseteq\limsup_{n\to\infty}E_nを示す

$ x \in \liminf_{n\to\infin}E_nと仮定する

$ \iff \exist k \geq 1. \forall n \geq k. x \in E_n

$ \forall n \geq kより、$ \exist n \geq k. x \in E_n.

示せなかった。(下で示した)

正しいことはわかるけど、どう書いていいかが思い浮かばないbiwa.icon

takker.icon

$ \sout\forall xにて

$ \sout{x \in \liminf_{n\to\infin}E_n}

$ \sout{\iff \exist k\in\N \forall n \geq k;x \in E_n}

$ \sout{\implies \forall k\in\N \exists n \geq k;x \in E_n}

$ \sout{\iff x \in \limsup_{n\to\infin}E_n}

$ \sout{\therefore\liminf_{n\to\infty}E_n\subseteq\limsup_{n\to\infty}E_n}

反則技みたいなことしてすまんかった

実は$ \sout{\exists a\forall b.P(a,b)\implies\forall a\exist b.P(a,b)}が成立するのでこんなことができてしまうのだ

こういう論理操作どこまでやっていいのか悩むbiwa.icon

いくらでもやって良い

不安なら証明すればoktakker.icon

証明すれば納得感出る

核心部の証明を丸投げしたとも言う

なるほどbiwa.icon

ごめんミスった！内田 1章集合と写像#646b36df1280f000003d7f18は成立しないtakker.icon

↓と間違えた

https://kakeru.app/33a55f8aeb212085f7e128537c4ca32c https://i.kakeru.app/33a55f8aeb212085f7e128537c4ca32c.svg

皆さん、証明は大事です

修正

$ \forall xにて

$ x \in \liminf_{n\to\infin}E_n

$ \iff \exist k\in\N \forall n \geq k;x \in E_n

$ \iff \forall m\in\N\exist k\in\N \forall n \geq k;x \in E_n

$ \implies \forall m\in\N\exist k\in\N ;x \in E_{\max\{m, k\}}

$ nに$ \max\{m,k\}を代入した

$ \iff\forall m\in\N\exist k,l\in\N;x\in E_l\land l=\max\{m,k\}\ge m

$ \implies\forall m\in\N\exist l\in\N;x\in E_l\land l\ge m

$ \iff\forall m\in\N\exist l\ge m;x\in E_l

$ \iff x\in\limsup_{n\to\infty}E_n

$ \therefore \liminf_{n\to\infty}E_n\subseteq\limsup_{n\to\infty}E_n

どうやって発想したか

任意のkに対してE_nを選択することを考えてた

あるよ！k以上のnが！

$ \forall m\ge l;x\in E_mだから、$ k,lより大きい

僕の回答も貼っておきます(頑張って考えたので)biwa.icon

+1!takker.icon

$ x \in \liminf_{n\to\infin}E_nと仮定する

$ \iff \exist k \geq 1. \forall n \geq k. x \in E_n.

$ kを$ k'とする。

$ \forall n \geq k'. x \in E_n.

$ j \geq k'となる自由変数$ jを取る

自由変数を取るで合ってる？biwa.icon

$ \forall,\exist,\sum,\intなどで束縛されてなければ、自由変数だとしていいと思うtakker.icon

なるほどbiwa.icon

自由変数をとった後、そのまま全称導入していいんでしたっけbiwa.icon

推論規則上はそれでよかったはずtakker.icon

https://ja.wikipedia.org/wiki/普遍汎化

よかった、ありがとうbiwa.icon

$ \exist m \geq j. x \in E_m.

$ \forall n \geq k'.x \in E_nと

$ j \geq k'より

任意の$ n \geq k'について、$ x \in E_nを満たすので、$ k'より大きい$ jについても同様に満たすよね

また、$ j \geq k' \land k' \geq 1なので、$ j \geq 1.

↑から↓の間が気になるtakker.icon

↑までに示せた式は$ j\ge k'\implies\exist m \geq j. x \in E_m

いや、特に問題はないか？

で、$ j\ge k'\ge1を使って$ k'を消すことにより、一番外側の$ \exists kを取り外せるようになる、ということかな

やっぱ気になったので式書く

$ \exist k \geq 1. \forall n \geq k. x \in E_n

$ \implies\exist k' \geq 1. \forall j\ge k'\forall m \geq j. x \in E_m

$ \implies\exist k' \geq 1. \forall j\ge k'\exists m \geq j. x \in E_m

$ \forall x.P(x)\implies\exists x.P(x)は成り立つ？

古典論理なら成り立ちそう

成立したはずbiwa.icon

さんくすtakker.icon

全称->具体化(全称削除)->存在導入、みたいな手順で証明できるbiwa.icon

これは自然演繹での話

https://wiis.info/math/logic/predicate-logic/existential-introduction/ の例に載ってる(任意の命題についてではないけれど)

ここから$ \exist k' \geq 1. \forall j\ge1\exists m \geq j. x \in E_mに持っていくとこがまずそう

$ \forall j\ge k'を$ \forall j\ge 1に拡大できない

$ k'>j\ge1で成立するかどうかがわからない

これbiwa.icon

ちゃんと手書きして書いてる途中で気づいたbiwa.icon

てか、成立するかわからんので、ここが存在部分になるよなbiwa.icon

($ k以下の範囲についての$ E_n)

https://gyazo.com/dfbea8000b8bcb71fbed6149da53bd4a

こういうことを言いたい

少なくとも自由変数$ jが$ k'以上では成立する。

都合がよい$ mを構成すれば良い。

$ mは必ず、$ k'より大きい。

$ jと$ k'で大きい方を取ればいい

これでtakkerさんの証明に繋がった

うおー気持ちいい

ちゃんと書くかbiwa.icon

ちょっと手書きします(iPad充電中)

終わった

書いてる途中でミスに気づいた

$ \forall j \geq 1. \exist m \geq j. \ x \in E_m.

$ \iff x \in \limsup_{x \to \infin} E_n.

$ x \in \liminf_{n\to\infin}E_n \implies x \in \limsup_{x \to \infin} E_n,

$ \iff \liminf_{n\to\infty}E_n\subseteq\limsup_{n\to\infty}E_n.

新たな証明(手書き)biwa.icon

https://gyazo.com/bc8af0c9c0f5012f87d44e2aa48297cf

うん、いい感じだ。

そして多分takker.iconさんの証明と同じになった

存在を言いたいときは、そのような値を構成する方法を考えることが大事なんだなと学習しましたbiwa.icon

良い学びを得た

この構成法はε-δ論法でよく使いますtakker.icon

$ Nを構成するやつだbiwa.icon

先生に答え合わせしてもらって正しいとお墨付きをもらった。

すばらしいtakker.icon*2

このあたりプログラミングとかなり似ているtakker.icon

「アルゴリズムを組み立てる」↔「$ jに対応する$ mを拾ってくる」

「コードに落とし込む」↔「論理式に書き起こす」

とりあえずイメージ貼っておこ

https://gyazo.com/0666059fb3bd752c6e7ad658bfa6dc87

(2)

$ x \in \limsup_{n\to\infin}A_nと仮定する

$ \iff \forall k \geq 1. \exist n \geq k. x \in A_n,

$ \implies \forall k \geq 1. \exist n \geq k. x \in B_n,

$ A_n \subset B_nより、$ x \in A_n \implies x \in B_n.だから

$ \iff x \in \limsup_{n\to\infin}B_n.

$ \liminf_{n \to \infin}A_n \subset \liminf_{n \to \infin}B_nについても同様に解けそう

問5.7

以下を示す

$ (\forall n\in\N.E_n\subseteq E_{n+1})\implies\lim_{n\to\infty}E_n=\bigcup_{n\in\N} E_n

$ \forall n\in\N.E_n\subseteq E_{n+1}を使って、

$ (\exist k\in\N \forall n \geq k. x \in E_n)\iff(\forall k\in\N\exist n\ge k.x\in E_n)\iff (\exists n\in\N.x\in E_n)

式が長いので、$ P\iff Q\iff Rと表すことにする

を示せばいい

問5.6で$ P\implies Qを示してある

あとは$ Q\implies R\implies Pを示せばおしまい

証明

$ Q\implies R

$ \forallをとるだけ。終了

$ R

$ \implies\exist k\in\N.

$ x\in E_k

$ \land\forall n\ge k.(x\in E_n\implies x\in E_n\subseteq E_{n+1})

$ \implies\exist k\in\N\forall n\ge k. x\in E_n

数学的帰納法を使った

$ \iff R

$ \therefore P\iff Q\iff R

$ \therefore \limsup_{n\to\infty}E_n=\liminf_{n\to\infty}E_n=\bigcup_{n\in\N}E_n

$ \underline{\iff \lim_{n\to\infty}E_n=\bigcup_{n\in\N}E_n\quad}_\blacksquare

$ (\forall n\in\N.E_n\supseteq E_{n+1})\implies\lim_{n\to\infty}E_n=\bigcap_{n\in\N} E_n

上と同じようにやればOK

(略)

そんなにむずくないが、証明を書くにはこの端末はあまりに貧弱すぎるtakker.icon

フリック入力じゃ数式かけない

問5.9

$ E_k:=\begin{dcases}A&\text{if }k\text{ is even}\\B&\text{if }k\text{ is odd}\end{dcases}のとき、以下が成り立つことを示す

$ \limsup_{n\to\infty}E_n=A\cup B

$ \liminf_{n\to\infty}E_n=A\cap B

takker.icon

$ x \in \limsup_{n\to\infin}E_n\iff \forall k\in\N\exist n\ge k. x \in E_nだから、以下を示せればいい

$ (\forall k\in\N\exist n\ge k. x \in E_n)\iff x\in A\cup B

証明

$ x \in \limsup_{n\to\infin}E_n

$ \iff\forall k\in\N\exist n\ge k. x \in E_n

$ \implies \exist n\in\N. x \in E_n

$ \iff \exist k\in\N. (x \in E_{2k}\lor x \in E_{2k+1})

$ \iff \exist k\in\N. (x \in A\lor x \in B)

$ \iff x\in A\cup B

$ \iff \forall k\in\N.x\in E_{2k}\cup E_{2k+1}

$ \iff \forall k\in\N.

$ \begin{dcases}\exist n\ge k.(x\in E_n\land n=2k)\\\exist n\ge k.(x\in E_n\land n=2k+1)\end{dcases}

ここミスってる

あとで直す

$ \implies \forall k\in\N.

$ \begin{dcases}\exist n\ge k.x\in E_n\\\exist n\ge k.x\in E_n\end{dcases}

$ \iff\forall k\in\N\exist n\ge k. x \in E_n

$ \iff x \in \limsup_{n\to\infin}E_n

$ \underline{\therefore \limsup_{n\to\infty}E_n=A\cup B\quad}_\blacksquare

全部$ \iffでつなぎたい

できるかな？

SS6 全射・単射

定義

$ f: A \to B.

全射

任意のbについて、b = f(a)となるような、aが必ず存在する

$ \forall b. \exist a. b = f(a).

影になる場所がない

単射

$ a_1 \not = a_2の時、$ f(a_1) \not = f(a_2)

f(a)があれば、1:1

全単射

全射かつ単射

逆写像

$ f^{-1}: B \to A.

ある関数の逆写像の存在と、ある関数と逆写像が全射像であることは同値

問6.3

$ \exist n \in \N. \exist x \in X.x = h^n(x)を証明する

$ Xは有限集合

$ h: X \to X.

証明

$ X = \{x_1, x_2, \dots, x_k\}とする。

$ Y = \{x_1, h(x_1), h^2(x_1), \dots, h^k(x_1)\}とする。

$ \exist y \in Y. x = y.

関数$ f: X \to Yは、単射ではないから、必ず$ f(x) = f(x_1)となるような値がある

単射でないと言える理由

$ |A| < |B|の時、関数$ f: A \to Bは単射ではない

ここで鳩の巣原理を使っているtakker.icon

数学的帰納法を使って証明できる

$ x_1 = yとなるような、$ x_1を$ xとする

$ yを$ h^n(x)とする。

よって、$ \exist n \in \N. \exist x \in X.x = h^n(x).

takker.icon

$ X は有限集合$ \iff\exists n\ge0\exists f:[0,n]\to X.f\text{は全単射}

任意の有限集合$ Xについて、$ \forall h:X\to X\exist n\in\N\exists x\in X.x=h^n(x)を証明できればいい

SS7 濃度の大小

問7.2

$ B^Aを$ f:A\to B全体の集合とする

テキストと表記変えたtakker.icon

配置集合とも呼ぶ

$ \forall A,B,C.C^{A\times B}\sim \left(C^B\right)^Aを示せ

takker.icon

$ {\cal F}:C^{A\times B}\ni f\mapsto (a\mapsto(b\mapsto f(a,b)))\in\left(C^B\right)^Aという写像を作れる

カリー化というやつ

これが全単射であることを示せばいい

全射と単射を示すのめんどいので、逆写像の存在を示して終わりにする

証明

$ {\cal F}:C^{A\times B}\ni f\mapsto (a\mapsto(b\mapsto f(a,b)))\in\left(C^B\right)^A

$ {\cal G}:\left(C^B\right)^A\ni f\mapsto ((a,b)\mapsto f(a)(b))\in C^{A\times B}

とする。$ \forall f:A\times B\to C.{\cal G}\circ{\cal F}(f)=fなので、$ \forall A,B,C.C^{A\times B}\sim \left(C^B\right)^Aである。

おわり

定理7.2

うわでたtakker.icon

写像の組み立てで発狂するやつ

そろそろやりたい

今週、濃度の大小に入りますbiwa.icon

わーいtakker.icon

$ \forall A, B.\left[\begin{cases}\exists f:A\rightarrowtail B\\\exists f:B\rightarrowtail A\end{cases}\implies\exists f:A⤖ B\right]

証明

書き写しただけtakker.icon

$ \begin{cases}\exists f:A\rightarrowtail B\\\exists g:B\rightarrowtail A\end{cases}

$ \implies\exists f:A\rightarrowtail B\exists g:B\rightarrowtail A.

$ \begin{cases}f\left[A\setminus\bigcup_{n\in\N}A_n\right]=B\setminus\bigcup_{n\in\N}B_n\\g\left[\bigcup_{n\in\N}B_n\right]=\bigcup_{n\in\N}A_n\end{cases}

ここで、

$ B_0:=B\setminus f[A]

$ A_0:=g[B_0]

$ B_1:= f[A_0]

...

$ B_n:=\begin{dcases}B\setminus f[A]&\text{if }n=0\\f[A_{n-1}]&\text{otherwise}\end{dcases}

$ A_n:=g[B_n]

とした

証明

$ f\left[A\setminus\bigcup_{n\in\N}A_n\right]

$ = \left\{b\in B|\exist a\in A\setminus\bigcup_{n\in\N}A_n.b=f(a)\right\}

$ = \left\{b\in B|\exist a\in A.b=f(a)\land\lnot\exist n\in\N.a\in A_n\right\}

$ B\setminus\bigcup_{n\in\N}B_n

$ =\{b\in B|\lnot\exist n\in\N.b\in B_n\}

新しい写像を作る

$ F:A\setminus\bigcup_{n\in\N}A_n\ni a\mapsto \left.f\right|_{B\setminus\bigcup_{n\in\N}B_n}(a)\in B\setminus\bigcup_{n\in\N}B_n

$ G:\bigcup_{n\in\N}B_n\ni b\mapsto \left.g\right|_{\bigcup_{n\in\N}A_n}(b)\in\bigcup_{n\in\N}A_n

$ F,Gは全単射である

証明

この時、

$ f^\dagger:A\ni a\mapsto\begin{dcases}F(a)&\text{if }a\notin\bigcup_{n\in\N}A_n\\G^{-1}(a)&\text{otherwise}\end{dcases}\in B

は全単射なので

$ \therefore \exists f:A⤖ B